#include <vector>

using namespace std;

// 到达角落需要移除障碍物的最小数目
// 给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n
// 每个单元格都是两个值之一：
// 0 表示一个 空 单元格，
// 1 表示一个可以移除的 障碍物
// 你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。
// 现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) 
// 返回需要移除的障碍物的最小数目
// 测试链接 : https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner/

// 坐标压缩
class Solution 
{
public:
    int minimumObstacles(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist); // 将 dist 中的元素设置成无穷大
        
        int move[] = {-1, 0, 1, 0, -1};
        deque<int> q;
        q.emplace_front(0);
        dist[0][0] = 0;
        while(!q.empty())
        {
            // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
            // 记 pos = x * n + y，则 x = pos / n，y = pos % n  
            int pos = q.front();
            q.pop_front();
            int x = pos / n, y = pos % n;
            if(x == m - 1 && y == n - 1) return dist[x][y];
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + move[k], ny = y + move[k + 1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n)
                {
                    int w = grid[nx][ny];
                    if(dist[nx][ny] > dist[x][y] + w)
                    {
                        dist[nx][ny] = dist[x][y] + w;
                        // 0 : 队头进  1 : 队尾进
                        w == 0 ? q.emplace_front(nx * n + ny) : q.emplace_back(nx * n + ny);
                    }
                }
            }
        }    
        return -1;
    }
};

// 使用 pair 来表示坐标
class Solution 
{
public:
    int minimumObstacles(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        int dist[m][n];
        memset(dist, 0x3f, sizeof dist); // 将 dist 中的元素设置成无穷大
        
        int dx[4] = {0, 0, -1, 1};
        int dy[4] = {-1, 1, 0, 0}; 
        deque<pair<int, int>> q;
        q.emplace_front(0, 0);
        dist[0][0] = 0;
        while(!q.empty())
        {
            auto [x, y] = q.front();
            q.pop_front();
            if(x == m - 1 && y == n - 1) return dist[x][y];
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + dx[k], ny = y + dy[k];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n)
                {
                    int w = grid[nx][ny];
                    if(dist[nx][ny] > dist[x][y] + w)
                    {
                        dist[nx][ny] = dist[x][y] + w;
                        // 0 : 队头进  1 : 队尾进
                        w == 0 ? q.emplace_front(nx, ny) : q.emplace_back(nx, ny);
                    }
                }
            }
        }    
        return -1;
    }
};